package leetcode;

/*
453. 最小移动次数使数组元素相等
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。
示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class problems_453 {
    public static void main(String[] arge) {
        System.out.println(new Solution().minMoves(new int[]{13,18,3,10,35,68,50,20,50}));
    }
    static public class Solution {
        // 思路，如果只有2个数，那么移动次数就只是两数之差
        // 然后依次处理，第三个数时，前2个数的结果是大的数字加上相差的数字
        public int minMoves(int[] nums) {
            // 首先排序
            Arrays.sort(nums);
            int count = 0;
            // 从第到高排序
            for (int i = 1; i < nums.length; i++) {
                // 需要移动次数是小到大
                int diff = nums[i] - nums[i-1] + count;
                nums[i] += count;
                count += diff;
            }
            return count;
        }
    }


//    // 超时
//    static class Solution {
//        public int minMoves(int[] nums) {
//            int num = 0;
//            Arrays.sort(nums);
//            while (nums[0] != nums[nums.length - 1]) {
//                for (int i = 0; i < nums.length - 1; i++) {
//                    nums[i]++;
//                }
//                Arrays.sort(nums);
//                num++;
//            }
//            return num;
//        }
//    }
}